package com.project.design.algorithm;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {

    public Integer[] shellSort(Integer[] str) {
        long start = System.currentTimeMillis();
        int len = str.length;
        for (int i = (int) Math.floor(len / 2); i > 0; i = (int) Math.floor(i / 2)) {
            for (int j = i; j < len; j++) {
                int k = j;
                Integer current = str[j];
                while (k - i >= 0 && current < str[k - i]) {
                    str[k] = str[k - i];
                    k = k - i;
                }
                str[k] = current;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("耗时："  + (end - start));
        return str;
    }

    public  Integer[] shellSortNew(Integer[] str){
        long start = System.currentTimeMillis();
        int len = str.length;
        while (true){
            len /= 2;
            for (int i = 0; i < len; i++) {
                for (int j = i + len; j < str.length; j +=len) {
                    int k = j - len;
                    while (k >=0 && str[k] > str[k + len]){
                        int temp = str[k + len];
                        str[k + len] = str[k];
                        str[k] = temp;
                        k -= len;
                    }

                }
            }
            if (len == 1){
                break;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("耗时："  + (end - start));
        return str;
    }
}
